package independentsetproblem;

import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.alg.NeighborIndex;

import java.util.ArrayList;
import java.util.List;

public class Cliques
{
    //number of steps
    private int steps;
    private UndirectedGraph<Vertex, DefaultEdge> g;
    //set of vertices which constitutes a complete subgraph
    private ArrayList<Vertex> currentClique;
    //MaxClique on current step
    private ArrayList<Vertex> leader;
    //number of cliques
    private int count;


    public Cliques(UndirectedGraph<Vertex, DefaultEdge> gr)
    {
        steps = 0;
        currentClique = new ArrayList<Vertex>();
        leader = new ArrayList<Vertex>();
        g = gr;
        count = 0;
    }

    /**
     * cand - candidates for further expansion of the present clique
     * subg - subgraph
     */
    public void expand(List<Vertex> subg, List<Vertex> cand)
    {
        if(subg.isEmpty())
        {
            //represents that Q is maximal clique
            steps++;
            if(currentClique.size()>=leader.size())
            {
                //System.out.println("Larger or the same size independent set is found!!! " + currentClique.toString());
                leader.clear();
                leader.addAll(currentClique);
            }
            count++;
        }
        else
        {
            ArrayList<Vertex> u = neighbourhood(subg,cand);
            NeighborIndex<Vertex,DefaultEdge> n = new NeighborIndex<Vertex,DefaultEdge>(g);
            ArrayList<Vertex> difference = new ArrayList<Vertex>(cand);
            difference.removeAll(intersection(cand,u));
            while(!difference.isEmpty())
            {
                Vertex expandingVertex = difference.get(0);
                steps++;
                currentClique.add(expandingVertex);
                //N(q)
                List<Vertex> neighbours = n.neighborListOf(expandingVertex);
                //next step of search
                expand(intersection(neighbours,subg),
                        intersection(neighbours,cand));
                //q is considered
                cand.remove(expandingVertex);
                difference.remove(expandingVertex);
                steps++;
                currentClique.remove(expandingVertex);
            }

        }
    }
    
    
    /**
     * N(u), with u: vertex in SUBG which maximizes |intersection(CAND, N(u))|
     */
    private ArrayList<Vertex> neighbourhood(List<Vertex> subg, List<Vertex> cand)
    {
        ArrayList<Vertex> neighbours = new ArrayList<Vertex>();
        NeighborIndex<Vertex,DefaultEdge> n = new NeighborIndex<Vertex,DefaultEdge>(g);
        int maxSize  = 0;
        for (Vertex v : subg)
        {
            List<Vertex> neighbourhood = n.neighborListOf(v);
            ArrayList<Vertex> candIntersection = intersection(neighbourhood, cand);
            if(candIntersection.size() > maxSize)
            {
                neighbours = new ArrayList<Vertex>(neighbourhood);
                maxSize = candIntersection.size();
            }
        }
        return neighbours;
    }

    /**  
     * Marks the largest cluque in the source graph
     */
    public void markClique()
    {
        System.out.println("\n"+"Largest independent set is found: " + leader.toString());
        System.out.println("\n"+"Largest independent set is being marked");     
        for(Vertex v : g.vertexSet())
        {
            if(leader.contains(v))
            {
                v.addToMaxIndSet();
            }
        }
    }

    private ArrayList<Vertex> intersection(List<Vertex> a, List<Vertex> b)
    {
        ArrayList<Vertex> result = new ArrayList<Vertex>(a);
        result.retainAll(b);
        return result;
    }

    public void result()
    {
        System.out.println("\n"+"Finished!"+"\n");
        System.out.println("Size of the largest independent set: " + leader.size());
        System.out.println("Number of maximal independent sets: " + count);
        System.out.println("Number of steps: " + steps);
    }

    public UndirectedGraph<Vertex, DefaultEdge> getGraph()
    {
        return g;
    }
}


